"""4.最长子序列和问题，采用分治法、蛮力法"""
def max_subarray_brute_force(arr):
    """
    蛮力法解决最长子序列和问题
    时间复杂度: O(n^2)
    """
    n = len(arr)
    max_sum = float('-inf')
    start_idx = end_idx = 0

    for i in range(n):
        current_sum = 0
        for j in range(i, n):
            current_sum += arr[j]
            if current_sum > max_sum:
                max_sum = current_sum
                start_idx = i
                end_idx = j

    return max_sum, start_idx, end_idx


def max_subarray_divide_conquer(arr, left=0, right=None):
    """
    分治法解决最长子序列和问题
    时间复杂度: O(n log n)
    """
    if right is None:
        right = len(arr) - 1

    # 基本情况：只有一个元素
    if left == right:
        return arr[left], left, right

    # 分：将数组分成两半
    mid = (left + right) // 2

    # 递归求解左右两半的最大子序列和
    left_sum, left_start, left_end = max_subarray_divide_conquer(arr, left, mid)
    right_sum, right_start, right_end = max_subarray_divide_conquer(arr, mid + 1, right)

    # 求解跨越中点的最大子序列和
    cross_sum, cross_start, cross_end = max_crossing_subarray(arr, left, mid, right)

    # 合并：返回三者中的最大值
    if left_sum >= right_sum and left_sum >= cross_sum:
        return left_sum, left_start, left_end
    elif right_sum >= left_sum and right_sum >= cross_sum:
        return right_sum, right_start, right_end
    else:
        return cross_sum, cross_start, cross_end


def max_crossing_subarray(arr, left, mid, right):
    """
    寻找跨越中点的最大子序列和
    """
    # 向左扩展找最大和
    left_sum = float('-inf')
    current_sum = 0
    max_left = mid

    for i in range(mid, left - 1, -1):
        current_sum += arr[i]
        if current_sum > left_sum:
            left_sum = current_sum
            max_left = i

    # 向右扩展找最大和
    right_sum = float('-inf')
    current_sum = 0
    max_right = mid + 1

    for i in range(mid + 1, right + 1):
        current_sum += arr[i]
        if current_sum > right_sum:
            right_sum = current_sum
            max_right = i

    return left_sum + right_sum, max_left, max_right


def max_subarray_kadane(arr):
    """
    Kadane算法（动态规划）解决最长子序列和问题
    时间复杂度: O(n)
    """
    max_so_far = arr[0]
    max_ending_here = arr[0]
    start = 0
    end = 0
    temp_start = 0

    for i in range(1, len(arr)):
        if max_ending_here + arr[i] > arr[i]:
            max_ending_here += arr[i]
        else:
            max_ending_here = arr[i]
            temp_start = i

        if max_ending_here > max_so_far:
            max_so_far = max_ending_here
            start = temp_start
            end = i

    return max_so_far, start, end


# 测试最长子序列和问题
print("=== 最长子序列和问题测试 ===")
arr = [-2, 1, -3, 4, -1, 2, 1, -5, 4]
print(f"数组: {arr}")

brute_sum, brute_start, brute_end = max_subarray_brute_force(arr)
print(f"蛮力法: 和={brute_sum}, 子序列={arr[brute_start:brute_end + 1]}")

dc_sum, dc_start, dc_end = max_subarray_divide_conquer(arr)
print(f"分治法: 和={dc_sum}, 子序列={arr[dc_start:dc_end + 1]}")

kadane_sum, kadane_start, kadane_end = max_subarray_kadane(arr)
print(f"Kadane算法: 和={kadane_sum}, 子序列={arr[kadane_start:kadane_end + 1]}")
print()